package com.huangyi;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        //字母大小写全排列
        class Solution1 {
            StringBuffer path;
            List<String> ret;
            String s;

            public List<String> letterCasePermutation(String _s) {
                path = new StringBuffer();
                ret = new ArrayList<>();
                s = _s;
                dfs(s, 0);
                return ret;
            }

            public void dfs(String s, int pos) {
                if (pos == s.length()) {
                    ret.add(path.toString());
                    return;
                }

                char ch = s.charAt(pos);
                // 原样加入
                path.append(ch);
                dfs(s, pos + 1);
                path.deleteCharAt(path.length() - 1);

                // 如果是字母，再切换大小写
                if (('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z')) {
                    char tmp = change(ch);
                    path.append(tmp);
                    dfs(s, pos + 1);
                    path.deleteCharAt(path.length() - 1);
                }
            }

            public char change(char ch) {
                if ('a' <= ch && ch <= 'z') return (char)(ch - 32);
                else return (char)(ch + 32);
            }
        }

        //优美的排列
        class Solution2 {
            int ret;
            boolean[] vis;

            public int countArrangement(int n) {
                ret = 0;
                vis = new boolean[n + 1]; // 使用 1..n
                dfs(n, 1);
                return ret;
            }

            public void dfs(int n, int pos) {
                // 放完 1..n 个位置，计数并立即返回
                if (pos > n) {
                    ret++;
                    return; // 易错点：必须 return，避免继续枚举 pos = n+1 的分支
                }

                for (int x = 1; x <= n; x++) {
                    if (!vis[x] && (x % pos == 0 || pos % x == 0)) {
                        vis[x] = true;
                        dfs(n, pos + 1);
                        vis[x] = false;
                    }
                }
            }
        }
    }
}